#include "binaryHeap.h"
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cmath>

using namespace std;

Heap::Heap()
{
	//heap = NULL;
	numElements = 0;
	heapSize = 0;
}

Heap::~Heap()
{
	//free(heap);
}

void Heap::swap(int p1, int p2)
{
        pos[key(p1).getName()] = p2;
        pos[key(p2).getName()] = p1;

	Vertex aux(0,0);
	aux = heap[p1];
	heap[p1] = heap[p2];
	heap[p2] = aux;
}

int Heap::root(int position)
{
	return 0;
}

int Heap::father(int position)
{
	return ceill((position-1)/2);
}

Vertex Heap::key(int position)
{
	return heap[position];
}

int Heap::left(int position)
{
	return 2*position + 1;
}

int Heap::right(int position)
{
	return 2*position + 2;
}

void Heap::heapfy_up(int p)
{
	int aux;
	numHeapUp++;
	if (p != root(p) && key(father(p)).getDist() > key(p).getDist())
	{		
		swap(father(p), p);
		heapfy_up(father(p));
	}
}

void Heap::heapfy_down(int p)
{
    	numHeapDown++;
    	if(left(p)+1 > numElements) {
		return;
    	} else if(left(p)+1 == numElements) {
		if(key(left(p)).getDist()<key(p).getDist())
            		swap(left(p), p);
    	}else if(key(p).getDist() > key(left(p)).getDist() || key(p).getDist() > key(right(p)).getDist())
	{
		if(key(left(p)).getDist() < key(right(p)).getDist())
		{
			swap(left(p), p);
			heapfy_down(left(p));
		}
		else
		{
			swap(right(p), p);
			heapfy_down(right(p));
		}
	}
}

void Heap::incert(int n, int d)
{
	Vertex v(n,d);
	numHeapUp=0;
	numHeapDown=0;
	numElements++;
	heap.push_back(v);

	if(v.getName()+1 > (int)pos.size()){
		for(int i = pos.size(); i <= v.getName(); i++){
                        pos.push_back(0);
                }
        }
        pos[v.getName()] = numElements-1;

	heapfy_up(numElements-1);
 }

void Heap::incert(Vertex v)
{
	numElements++;
        numHeapUp=0;
	numHeapDown=0;
	heap.push_back(v);

	if(v.getName()+1 > (int)pos.size()){
                for(int i = pos.size(); i <= v.getName(); i++){
                        pos.push_back(0);
                }
        }
	pos[v.getName()] = numElements-1;

	heapfy_up(numElements-1);
}

void Heap::checkHeap(int p)
{
    if(p < numElements-1){
        if(left(p)+1 == numElements){
            if(key(p).getDist() > key(left(p)).getDist())
                cout << "heap error" << endl;
        } else if(left(p)+1 < numElements){
            if(key(p).getDist() > key(left(p)).getDist())
                cout << "heap error" << endl;
            if(key(p).getDist() > key(right(p)).getDist())
                cout << "heap error" << endl;
            checkHeap(left(p));
            checkHeap(right(p));
        }
    }
}

Vertex Heap::deleteMin()
{
	Vertex v = heap[0];
	removeElement(0);

	return v;
}

void Heap::removeElement(int p)
{
	numElements--;
        numHeapDown=0;
	numHeapUp=0;
	//heap[p] = heap[numElements];
	swap(p, numElements);
	heap.pop_back();
	heapfy_down(p);
}

int Heap::findElementByKey_aux(Vertex k, int p)
{
        numFind++;
	if(key(p).getName() == k.getName()) {

		//printf("Igual Key(p) = %d, p = %d, k = %d\n", key(p).getName(), p, k.getName());
		return p;
	} else
	if(key(p).getDist() >  k.getDist()){
		//printf("Nao Existe Key(p) = %d, p = %d, k = %d\n", key(p).getName(), p, k.getName());
		return 0;
	} else
	if(left(p)+1 > numElements){
		//printf("Nao tem mais filhos Key(p) = %d, p = %d, k = %d\n", key(p).getName(), p, k.getName());
		return 0;
	} else

	if(left(p)+1 <= numElements && right(p)+1 <= numElements)
		return findElementByKey_aux(k, left(p)) + findElementByKey_aux(k, right(p));
	else return findElementByKey_aux(k, left(p));
}

int Heap::findElementByKey(Vertex v)
{
	numFind = 0;
	int p = findElementByKey_aux(v, 0);
	if(key(p).getName() != v.getName())
        cout << "Invalid key" << endl;
	return p;
}

void Heap::updatePosition(int p, Vertex v)
{
        numHeapUp=0;
        numHeapDown=0;
	if(key(p).getDist() > v.getDist())
	{
		heap[p] = v;
		heapfy_up(p);
	} else {
		heap[p] = v;
		heapfy_down(p);
	}
}

void Heap::updateKey(Vertex o, int n)
{
	Vertex v(o.getName(), n);
	//updatePosition(findElementByKey(o), v);
	updatePosition(pos[o.getName()], v);
}

void Heap::printHeap(int p)
{
    if(!isEmpty()){
	cout << p << " " << heap[p].getName() << " " << heap[p].getDist() << " " << heap[pos[heap[p].getName()]].getName() << endl;
	if(left(p)+1 <= numElements) printHeap(left(p));
	if(right(p)+1 <= numElements) printHeap(right(p));
    }
}


